package com.example.shortestpathalgorithm44;

import java.util.LinkedList;

/**
 * 回溯算法（穷举）
 * @auther lijiewei
 * @date 2022/7/14 11:57
 */
public class BacktrackingAlgorithm {

    //开始顶点id
    private int start;
    //结束顶点id
    private int end;
    //用来还原最短路径,值存储起点(指向当前节点)的下标
    private int[] predecessor;
    //领接表
    private LinkedList<Graph.Edge>[] adj;


    /**
     * 从顶点s到顶点t的所有路径
     * @param start id为start的顶点
     * @param end id为end的顶点
     * @return
     * @author lijiewei
     * @date   2022/7/13 11:43
     */
    public void backtracking(Graph graph, int start, int end) {
        this.start = start;
        this.end = end;
        this.adj = graph.getAdj();

        //用来还原最短路径,值存储起点(指向当前节点)的下标
        this.predecessor = new int[graph.getV()];

        handleNode(start, 0);
    }


    private void handleNode(int s, int w) {
        if (s == end) {
            //输出最短路径
            System.out.print(start);
            print(start, end, predecessor);
            System.out.println("=========总路径："+w);
            return;
        }

        //获取下一个顶点
        for (int i = 0; i < adj[s].size(); i++) {
            //取出一条以s为起点的边
            Graph.Edge edge = adj[s].get(i);
            predecessor[edge.tid] = edge.sid;
            handleNode(edge.tid, edge.w+w);
        }
    }


    private void print(int s, int t, int[] predecessor) {
        if (s == t) {
            return;
        }
        print(s, predecessor[t], predecessor);
        System.out.print(" -> " +t);
    }
}
